package com.zjsru.leetcode75.level1;

/**
 * @Author: cookLee
 * @Date: 2023-11-14
 * 多米诺和托米诺平铺
 */
public class NumTilings {

    /**
     * 主
     * \
     * 有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。
     * 给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。
     * 平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。
     * \
     * 输入: n = 3
     * 输出: 5
     * \
     * @param args args
     */
    public static void main(String[] args) {
        NumTilings numTilings = new NumTilings();
        int n = 3;
        System.out.println(numTilings.numTilings(n));
    }

    /**
     * 模
     */
    private static final long MOD = (long) 1e9 + 7;

    /**
     * num tilings
     *
     * @param n n
     * @return int
     */
    public int numTilings(int n) {
        if (n == 1) {
            return 1;
        }
        long[] nums = new long[n + 1];
        nums[0] = 1;
        nums[1] = 1;
        nums[2] = 2;
        for (int i = 3; i <= n; i++) {
            nums[i] = (2 * nums[i - 1] + nums[i - 3]) % MOD;
        }
        return Integer.parseInt(String.valueOf(nums[n]));
    }
}
